1. Field of Invention
In general, this invention relates to programming of computers with various kinds of facilities for parallel or other high capability execution of computer programs, is specifically to the automated generation of programs from execution platform neutral specifications, to the automated partitioning of those programs into pieces that can be executed in parallel or can otherwise exploit a high capability feature of a high capability execution platform architecture, and to the automated choice of the specific partition form that best exploits the parallelism or other high capability feature in a chosen class of parallel or other high capability execution platform architectures.
More specifically, this part of the invention relates to extending the notion of partitioning from the natural partitions (described in the U.S. Pat. No. 8,060,857) to synthetic partitions. Natural partitions describe the inherent, non-discretionary case structure of a target implementation and therefore allow little user choice in whether and how they manifest themselves in the target implementation. By contrast, synthetic partitions extend the machinery of partitions to impose additional constraints on the design features in the target implementation and therefore allow the user a wider range of choice in what design features are included in or excluded from the target implementation. A synthetic partition—in contrast to natural partitions—incorporates one or more design feature choices and is thus a method of requiring the appearance of one or more design features in the evolving target implementation without requiring the immediate act of manufacturing the concrete manifestation of those design features in programming language terms (i.e., in terms of convention programming languages such as C, C++ or Java).
Thus, like natural partitions, synthetic partitions act like a “to do” list, defining what design features will be in the code when it is eventually manufactured. By deferring the act of casting the design features into code immediately, the invention allows the generator to abstractly coordinate several, separately introduced sets of design features on that “to do” list without having to deal with the myriad of structures, relationships and details that would be introduce by a programming language expression of those design features. The invention can integrate, coordinate and manipulate the synthetic objects like atomic entities without having manipulating the extended code they will eventually engender, which is likely not to be atomic in nature and is often dispersed among remotely separated locales in the target implementation. For example, later in this application, a specific example will use a synthetic partition that introduces a framework for thread based parallelism such that the generated code will be spread across three separate routines and will be comprised of code segments that handle thread initialization, control and synchronization for some as yet specified, partitioned data structure. These three routines are skeletal with “holes” for the specific code segments to do the actual computation on the data structure. A separate set of partitions both natural and synthetic will supply code segments for these “holes” as well as some interstitial design tissue that connects and coordinates the skeletal routines with their computational payload or content. Dealing with these complex design features directly in terms of code representations would be so convoluted and complex as to be completely infeasible.
Abstractly speaking, the generator is planning and coordinating the construction of the integrated set of design features in the problem and programming process domain (using natural and synthetic partitions) rather than in the programming language domain (using code). This vastly simplifies the coordination and generation process.
2. Description of Prior Art
This patent application is a continuation-in-part of U.S. Pat. No. 8,060,857, Titled “Automated Partitioning of a Computation for Parallel or Other High Capability Architecture,” Ted J. Biggerstaff, Jan. 31, 2009.
This patent extends the U.S. Pat. No. 8,060,857 by extending the partition mechanism and the associated machinery as a mechanism for incrementally sketching the design of the evolving target program in abstract form before facing the challenges of creating and integrating the concrete details that are required by a programming language manifestation of the target program.
Key Machinery Much of the prior art is most easily understood by contrasting it with the key machinery and methods underlying this invention. Thus, the following several paragraphs provide a summary of the key machinery and methods of this invention to serve as a context for the subsequent descriptions of the prior art.
A hallmark of the methods and machinery of this invention, and one that breaks with the tradition of most of today's mechanisms for software generation and in particular, for software generation of parallel and other high capability software, is that this invention performs most of its key operations in the problem domain and the programming process or design domain but not (initially) in the general program language (GPL) domain. What this means is that this invention initially represents its end product largely in terms of problem data and operators (e.g., images and convolutions) and non-programming language oriented abstractions (e.g., associated programming constraints defined in patent Ser. No. 12/363,738) rather than is programming language data, operators and abstractions (e.g., concretely defined matrices, collections and arithmetic operations). (By way of definition, a convolution is a very general image or signal processing operation that computes output images or signals from input images or signals where each pixel or signal element in the output image or signal is computed from the corresponding input pixel or signal element along with the neighboring pixels or signal elements surrounding that particular input pixel or signal element.)
The invention formulates its output (i.e., the target program) first, in terms of broad-brush design abstractions (e.g., constraints that logically partition a computation into pieces). These design abstractions are easy to create, organize, combine and re-structure and do not yet contain the low level programming (i.e., GPL) details or organizational structure. Adding the GPL details and organizational structure later reduces one large, global and intractable programming problem to a set of locally separated, smaller and therefore simpler programming problems, each within the context of a separate design abstraction. In other words, operating in the problem, programming process, and design domain first, and adding the programming details later means “design first, code later.”
The invention expresses that design in terms of a Logical Architecture (LA) that captures the broad brush design in terms of constraints that put important limitations on the form that the final program will take without completely defining that final program at the level of detail and organization that a programming language would require. These constraints are a new kind of abstraction that breaks with traditional representations based on programming language concepts and allows design features to be added into the target program design in a step by step process that is not is restricted or ordered by the constructs and relationships of the programming language domain. This step by step process evolves the LA into a Physical Architecture (PA) that bit by bit develops the details and relationships that a programming language compiler requires.